"""
389. 找不同
简单
相关标签
相关企业
给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。



示例 1：

输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。
示例 2：

输入：s = "", t = "y"
输出："y"
"""
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        # dict_s = dict_t={}  这样错误，把dict_s和dict_t都指向了同一个对象
        # dict_s = {}
        # dict_t = {}
        # for item in s :
        #     if item not in dict_s.keys():
        #         dict_s[item] = 1
        #     else:
        #         dict_s[item]+=1
        # for item in t :
        #     if item not in dict_t.keys():
        #         dict_t[item] = 1
        #     else:
        #         dict_t[item]+=1
        # print(dict_s, dict_t)
        # for k,v in dict_t.items():
        #     if dict_s=={} or (k not in dict_s) or (dict_t[k]!=dict_s[k]) :
        #         return k
        """
        方法二，使用异或运算，
        原理：异或运算的性质
        交换律：a ^ b = b ^ a
        结合律：(a ^ b) ^ c = a ^ (b ^ c)
        恒等律：a ^ 0 = a
        自反律：a ^ a = 0
        架设s='abc' t='abcd' 那么把st的每个字符依次做异或运算就是0^a^b^c^a^b^c^d,那么就等价于0^a^a^b^b^c^c^d=0^0^0^d=0^d=d^0=d
        因为相同的会被抵消，所以没有被抵消的就是多的
        """
        i = 0
        for item in s:
            i^=ord(item)
        for item in t:
            i^=ord(item)
        return chr(i)

if __name__ == '__main__':
    print(Solution().findTheDifference(s = "abcd", t = "abcde"))